package day_2022_12_to_3.day;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/12/19 22:19
 **/
public class Day12_19_Num1971 {
    class Solution {
        public boolean validPath(int n, int[][] edges, int source, int destination) {
            List<Integer>[] adj = new List[n];
            for (int i = 0; i < n; i++) {
                adj[i] = new ArrayList<Integer>();
            }
            for (int[] edge : edges) {
                int x = edge[0], y = edge[1];
                adj[x].add(y);
                adj[y].add(x);
            }
            boolean[] visited = new boolean[n];
            return dfs(source, destination, adj, visited);
        }

        public boolean dfs(int source, int destination, List<Integer>[] adj, boolean[] visited) {
            if (source == destination) {
                return true;
            }
            visited[source] = true;
            for (int next : adj[source]) {
                if (!visited[next] && dfs(next, destination, adj, visited)) {
                    return true;
                }
            }
            return false;
        }
    }
}